package cn.z2huo.algorithm.greedy.backPack;

/*
*   背包问题
*   初始化的重量，价值数组中的顺序都是一一对应的
*   假设有n个物品，则每个物品只能向背包里面放依次
*   且如果这个物品不能全部放进去，可以放一个物品的一部分
*
*   分别计算各个物品的单位价值，然后按照单位价值进行排序
*   首先，判断单位价值最大的物品的总重量是否小于背包的剩余重量，满足条件将单位价值最大的物品放进去
*   然后，判断单位价值第二大的物品的总重量是小于背包的剩余重量，满足条件将单位价值最大的物品放进去
*   以此类推
*   当有一个物品的全部放不进去时，这就是边界条件，此时，将此物品的能放进去的放进去，之后结束
*
* */

public class Main {
    public float resolve(int[] weight, int[] value, float[] vpw, int capacity){
        // 计算物体单位重量的价值
        for(int i=0; i<weight.length; i++){
            float v = value[i]/weight[i];
            vpw[i] = v;
        }
        // 按照单位价值进行排序，总重量数组与价值数组也需要进行排序，使各个物品相互对应
        sort(weight, value, vpw);
        printArray(weight);
        printArray(value);
        printArray(vpw);

        // 计算所能达到的最大的价值
        float maxValue = 0;
        int usedCapacity = 0;
        // 按照单位价值数组进行遍历，从单位价值大的物品开始放
        for(int i=0; i<weight.length; i++){
            // 当背包的剩余容量可以放下此物品时
            if(weight[i]<=(capacity-usedCapacity)){
                maxValue += weight[i] * vpw[i];
                usedCapacity += weight[i];
            // 当背包不能将这个物品全部放进去时
            }else{
                maxValue += (capacity-usedCapacity)*vpw[i];
                break;
            }
        }
        return maxValue;
    }

    // 选择排序
    public void sort(int[] weight, int[] value, float[] vpw){
        for(int i=0; i<weight.length; i++){
            for(int j=i+1; j<weight.length; j++){
                if(vpw[j] > vpw[i]){
                    float flag = vpw[i];
                    vpw[i] = vpw[j];
                    vpw[j] = flag;

                    int flag2 = weight[i];
                    weight[i] = weight[j];
                    weight[j] = flag2;

                    flag2 = value[i];
                    value[i] = value[j];
                    value[j] = flag2;
                }
            }
        }
    }

    public void printArray(int[] array){
        for(int i=0; i<array.length; i++){
            System.out.printf("%4d", array[i]);
        }
        System.out.println();
    }
    public void printArray(float[] array){
        for(int i=0; i<array.length; i++){
            System.out.printf("%5.1f", array[i]);
        }
        System.out.println();
    }

    public static void main(String[] args){
        int capacity = 50;
        int[] weight = {10, 30, 20};
        int[] value = {60, 120, 100};
        float[] vpw = new float[weight.length];

        Main m = new Main();
        float result = m.resolve(weight, value, vpw, capacity);
        System.out.println("背包中所能放下物品的最大价值为：\n"+result);
    }
}